package main

import (
	"fmt"
	"strings"
)

// 实现栈 (stack) 数据结构：
// 它的格子包含数据，比如整数 i、j、k 和 l 等等，格子从底部（索引 0）至顶部（索引 n）来索引。这个例子中假定 n = 3，那么一共有 4 个格子。
// 一个新栈中所有格子的值都是 0。
// 将一个新值放到栈的最顶部一个空（包括零）的格子中，这叫做 push。
// 获取栈的最顶部一个非空（非零）的格子的值，这叫做 pop。 现在可以理解为什么栈是一个后进先出 (LIFO) 的结构了吧。
// 为栈定义一个 Stack 类型，并为它定义 Push 和 Pop 方法，再为它定义 String() 方法（用于调试）输出栈的内容，比如：[0:i] [1:j] [2:k] [3:l]。
// 1）stack_arr.go：使用长度为 4 的 int 数组作为底层数据结构。
// 2） stack_struct.go：使用包含一个索引和一个 int 数组的结构体作为底层数据结构，索引表示第一个空闲的位置。
// 3）使用常量 LIMIT 代替上面表示元素个数的 4 重新实现上面的 1）和 2），使它们更具有一般性。

const LIM = 4

type Stack [LIM]int

func (s *Stack) Push(d int) (b bool) {
	for i := LIM - 1; i >= 0; i-- {
		if s[i] != 0 {
			continue
		}
		s[i] = d
		b = true
		break
	}
	return
}

func (s *Stack) Pop() (d int) {
	for i := 0; i < LIM; i++ {
		if s[i] != 0 {
			d, s[i] = s[i], 0
			break
		}
	}
	return
}

func (s *Stack) String() string {
	str := ""
	for i := 0; i < LIM; i++ {
		str += fmt.Sprintf("[%d:%v] ", i, s[i])
	}
	return strings.TrimSpace(str)
}

func main() {
	s := &Stack{}

	s.Push(3)
	s.Push(5)
	s.Push(9)
	s.Push(13)
	fmt.Println("Stack String(): ", s)
	p := s.Pop()
	fmt.Println("After Pop(): ", p, " Stack is: ", s)
}
